package com.example.demo.suanfa_heap;

import org.junit.Test;

import java.util.PriorityQueue;

/**
 * @program: java_base
 * @description: 堆排序
 * @author: zhouhongtao
 * @happyCreateTime: 2022/02/16 10:24
 */
public class HeapSortDemo {

    @Test
    public void test01(){
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        heap.add(1);
        heap.add(1);
        heap.add(1);
        heap.add(1);
        heap.add(1);


        System.out.println(heap.size());
//        while (!heap.isEmpty()){
//            System.out.println(heap.poll());
//        }
        for (int i = 0; i < heap.size(); i++) {
            System.out.println(heap.poll());
        }
//        System.out.println(heap.poll());
//        System.out.println(heap.poll());
//        System.out.println(heap.poll());
//        System.out.println(heap.poll());
//        System.out.println(heap.poll());
//        System.out.println(heap.poll());
    }

    public void heapSort(int[] arr) {
        if (arr.length == 0) {
            return;
        }
        // O(N*logN)
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        // O(N)
        for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
        int heapSize = arr.length;
        swap(arr,0,--heapSize);
        while (heapSize>0){
            heapify(arr,0,heapSize);
            swap(arr, 0, --heapSize);
        }

    }

    // 新加进来的数，现在停在了index位置，请依次往上移动，
    // 移动到0位置，或者干不掉自己的父亲了，停！
    private void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }
    // 从index位置，往下看，不断的下沉
    // 停：较大的孩子都不再比index位置的数大；已经没孩子了
    private void heapify(int[] arr,int index,int heapSize){
        // 这个函数是，在保留arr[0]元素，arr[0] 和 arr[index]替换后，需要重新确定此大根堆的arr[0]位置的元素
        int leftIndex = index * 2 + 1;
        while (leftIndex < heapSize) {
            // 有向下走的趋势
            // 查看是否存在右节点 ，有孩子
            int maxIndex = index + 1 > heapSize ? index : index + 1;
            // 判断是选择左边得孩子？还是右边得孩子？// 是使用左边得？还是使用右边得index
            maxIndex = arr[leftIndex] > arr[maxIndex] ? leftIndex : maxIndex;
            // 判断 index 和 暂时得孩子节点得大小，确定 maxIndex
            maxIndex = arr[index] > arr[maxIndex] ? index : maxIndex;
            if (maxIndex == index){
                break;
            }
            if (arr[index] < arr[maxIndex]){
                swap(arr,index,maxIndex);
            }
            index = maxIndex;
            leftIndex = index * 2 + 1;
        }
    }

    private void swap(int[] arr, int index, int i) {
        int tmp = arr[index];
        arr[index] = arr[i];
        arr[i] = tmp;
    }

}
